package jjn.round1;

import java.util.*;

/**
 * @author Jjn
 * @since 2022-07-23 17:03
 */
public class LeetCode146_LRU {
    
    private final Map<Integer, Integer> map;
    private List<Integer> keys;
    private final int size;
    
    public LeetCode146_LRU(int capacity) {
        this.map = new HashMap<>(capacity);
        this.size = capacity;
        this.keys = new ArrayList<>(capacity);
    }
    
    public int get(int key) {
        Integer result = map.getOrDefault(key, -1);
        
        reArrangeElements(key);
        
        return result;
    }
    
    private void reArrangeElements(int key) {
        List<Integer> order = new ArrayList<>();
        order.add(key);
        for (Integer element : keys) {
            if (!Objects.equals(element, key)) {
                order.add(element);
            }
        }
        this.keys = order;
    }
    
    public void put(int key, int value) {
        // 已存在的元素
        if (map.containsKey(key)) {
            reArrangeElements(key);
        }
        // 新元素
        // LRU已满
        if (keys.size() > size) {
            // 去除最旧的
            Integer lastElement = keys.get(keys.size() - 1);
            map.remove(lastElement);
            keys.remove(lastElement);
        }
        map.put(key, value);
        reArrangeElements(key);
    }
}
